Dynamic Network Flows - Chapter 3: Optimal Dynamic Flows

\( \newcommand{\IN}{\mathbb{N}} \newcommand{\INs}{\mathbb{N}^\ast} \newcommand{\INo}{\mathbb{N}_0} \newcommand{\IZ}{\mathbb{Z}} \newcommand{\IRnn}{\IR_{\geq 0}} \newcommand{\IRsp}{\IR_{\gt 0}} \newcommand{\IR}{\mathbb{R}} \newcommand{\IC}{\mathbb{C}} \newcommand{\A}{\mathcal{A}} \newcommand{\B}{\mathcal{B}} \newcommand{\U}{\mathfrak{U}} \newcommand{\coloneqq}{:=} \newcommand{\coloniff}{:\iff} \newcommand{\Set}[1]{\left\{#1\right\}} \newcommand{\SMid}{\,\middle|\,} \newcommand{\set}[1]{\{#1\}} \newcommand{\sMid}{\,|\,} \newcommand{\PSet}[1]{2^{#1}} \newcommand{\supp}{\mathrm{supp}} \newcommand{\dist}[2]{\mathrm{dist}^c_{#1}(#2)} \newcommand{\dists}[2]{{\mathrm{dist}^c_{#1}}'(#2)} \newcommand{\Ind}{{\Large\raise{0pt}{\unicode{x1D7D9}}\,}} \newcommand{\bigO}{\mathcal{O}} \newcommand{\abs}[1]{\left|#1\right|} \newcommand{\norm}[1]{\left\|#1\right\|} \newcommand{\scalar}[2]{\left\langle #1,#2 \right\rangle} \newcommand{\rDeriv}{\partial_+} \newcommand{\lDeriv}{\partial_-} \newcommand{\queue}{q} \newcommand{\Pc}{\mathcal{P}} \newcommand{\Wc}{\mathcal{W}} \newcommand{\diff}{\mathrm{d}} \newcommand{\eps}{\varepsilon} \newcommand{\ql}[1][e]{Q_{#1}} \newcommand{\network}{N} \newcommand{\tauPmin}{\tau_{p_{\min}}} \newcommand{\fvals}[1]{\mathrm{value}(#1)} \newcommand{\fval}[1]{\mathrm{value}(#1)} \newcommand{\ccaps}[1]{\mathrm{capacity}(#1)} \newcommand{\fcosts}[1]{\mathrm{cost}(#1)} \newcommand{\edgesFrom}[1]{\delta^+(#1)} \newcommand{\edgesTo}[1]{\delta^-(#1)} \newcommand{\PathSet}{\mathcal{P}} \newcommand{\CycleSet}{\mathcal{C}} \)

Dynamic flow $f=(f^+_e,f^-_e)$ in dynamic flow network $N=(G,s,t,\nu,\tau)$ with capacities $\nu_e \gt 0$ and travel times $\tau_e \geq 0$:

with cumulative in-/outflow $F^\pm_e(\theta) \coloneqq \int_0^\theta f^\pm_e(\zeta)\diff\zeta$, value up to $T$: $\fval{f,T} \coloneqq \sum_{e \in \edgesTo{t}}F^-_e(T) - \sum_{e \in \edgesFrom{t}}F^+_e(T)$

respects capacities if $f^-_e(\theta) \leq \nu_e$ for almost all $\theta \in \IR$, $e \in E$
weak flow conservation at nodes if $\sum_{e \in \edgesFrom{v}}F^+_e(\theta) \leq \sum_{e \in \edgesTo{v}}F^-_e(\theta)$ for all $\theta \in \IR$, $v \neq s,t$
weak flow conservation at nodes and $\fval{f,\theta} \geq 0$ for all $\theta \in \IR$
strong flow conservation at nodes if $\sum_{e \in \edgesFrom{v}}F^+_e(\theta) = \sum_{e \in \edgesTo{v}}F^-_e(\theta)$ for all $\theta \in \IR$, $v \neq s,t$
weak flow conservation at nodes and $\fval{f,\theta}$ non-decreasing
weak flow conservation on edges if $F^-_e(\theta+\tau_e) \leq F^+_e(\theta)$ for almost all $\theta \in \IR$, $e \in E$
strong flow conservation on edges if $F^-_e(\theta+\tau_e) = F^+_e(\theta)$ for almost all $\theta \in \IR$, $e \in E$

Extreme Value Theorem: $K$ non-empty, compact, $\Phi: K \to \IR$ continuous
mmmmmmmmmmmmmmm $\implies$ $\exists x^* \in K: \Phi(x^*) = \sup\Set{\Phi(x) \SMid x \in K}$

$(x_e)$ static $s$,$t$-flow in $(G,s,t,\nu)$ with path-cycle-decomposition $(x_p)$
→ associated temporally repeated flow $f=(f^+_e)$ is direct dynamic flow corresponding to path-based dynamic flow \[f^+_p(\theta) \coloneqq \begin{cases}0, &\text{ if } \theta \lt 0 \\ x_p, &\text{ if } \theta \geq 0\end{cases}.\]

Lemma 3.11: $(x_e)$ feasible $s$,$t$-flow $\implies$ associated temp. rep. flow $f$ is feasible direct dynamic flow with

\[\fval{f,T} \geq T\cdot\fvals{x} - \sum_{e \in E}\tau_e x_e. \quad\quad (\#)\]

We have equality if $(x_e)$ has path-decomposition with $x_p=0$ for all $p \in \PathSet$ with $\tau_p \gt T$.

Lemma 3.12: $(x'_e)$ mincost flow in $\network'$, $(x_e)$ its restriction to $\network$ and $(x_p)$ a path-cycle decomposition. Then

$x_p \gt 0 \implies \tau_p \leq T$
$x_c \gt 0 \implies \tau_c = 0$
$(x_e)$ maximizes $T\cdot\fvals{x} - \sum_{e \in E}\tau_e x_e \quad\quad (\#)$

Dynamic Ford-Fulkerson-Algorithm:

Input: $s$,$t$-network $\network=(G,s,t,\nu,\tau)$, time horizon $T$
Output: maximum dynamic flow $(f^+_e,f^-_e)$ with until $T$

(1) Construct $\network'$ from $\network$ by adding edge $ts$ with $\tau_{ts}=-T$ and $\nu_{ts}=\infty$

(2) Compute min-cost flow $x'$ of value $0$ in $\network'$ (with $\tau_e$ as cost)

(3) Determine path-cycle decomposition $(x'_p)$ of restriction of $x'$ to $\network$

(4) Return: Temporally repeated flow $f$ associated with $(x_p)$

dynamic $s$,$t$-cut with time horizon $T$: $(\beta_v) \in \IR^V$ with $\beta_s=0$, $\beta_t \geq T$ mmmm $v$ on $t$-side before $\beta_v$, on $s$-side after $\beta_v$

feas. dyn. flow $f$ is quickest flow with value $v$ if $\exists T \geq 0: \fval{g,\theta} \lt v = \fval{f,T}$ f.a. $\theta \in [0,T)$ and feas. dyn. flows $g$.

Quickest Flow Algorithm:

Input: $s$,$t$-network $\network=(G,s,t,\nu,\tau)$, value $v$
Output: quickest flow $(f^+_e,f^-_e)$ with value $v$

(1) Repeat
(2) .. Guess time horizon $T$
(3) .. Compute maximum dynamic flow $f$ until $T$
(4) Until $\fval{f,T}=v$

Lemma 3.20: For any fixed network $\network$ the function
\[V: \IRnn \to \IRnn, T \mapsto \max\Set{\fval{f,T} \SMid \begin{array}{l}f \text{ a feas. dyn.}\\\text{flow in } \network\end{array}}\] is zero on $[0,\tauPmin]$ and strictly increasing on $(\tauPmin,\infty)$.

Earliest-Arrival Algorithm:

Input: dynamic flow network $\network=(G,s,t,\nu,\tau)$, time horizon $T$
Output: earliest arrival flow $f$ with time horizon $T$

(1) compute min-cost flow $y$ with ass. max. dyn. flow until $T$

(2) comp. min-cost flow $(x_p) \in \IRnn^{\PathSet^\leftrightarrow}$ of val. $\fvals{y}$ in $(G,s,t,\tau)$ by SSP

(3) def. gen. path-based dyn. flow $(f^+_p)$ by $f^+_p(\theta) \coloneqq x_p$ f.a. $\theta \geq 0$

(4) Return dynamic pseudo-flow coresponding to $(f^+_p)$